# Циклический алгоритм распределения задач

*Round-robin (круглая лента)* — алгоритм балансировки нагрузки вычислительной системы, распределение
задач по кругу между исполнителями. Есть ряд задач **m**, выполнение которых занимает равное время, и
ряд исполнителей **n**, равных по своим возможностям. Реализация алгоритма на Java 7 с использованием
одной карты `TreeMap` без внешних библиотек.

### Класс `CircularList<T>`

| Карта TreeMap |                                   |
|---------------|-----------------------------------|
| key           | `Integer` — количество обращений. |
| value         | `List<T>` — список исполнителей.  |

| Конструктор                  |                                                      |
|------------------------------|------------------------------------------------------|
| `CircularList(List<T> list)` | `list` — список исполнителей, обязательный параметр. |

| Доступные методы         | Возвращаемое значение                                                                 |
|--------------------------|---------------------------------------------------------------------------------------|
| `getOne()`               | `T`, первый элемент с наименьшим количеством обращений.                               |
| `getOne(List<T> filter)` | `T`, первый элемент с наименьшим количеством обращений, которого нет в списке отбора. |
| `getOne(T filterIn)`     | `T`, указанный элемент независимо от количества обращений.                            |
| `status()`, `toString()` | `String`, текущее состояние карты.                                                    |

| Закрытый метод |                                                                                   |
|----------------|-----------------------------------------------------------------------------------|
| `reset()`      | `void`, сбрасываем счётчики при достижении максимума `Integer` и обновляем карту. |

---

<details open>
<summary><h3 id="CircularList.java">CircularList.java</h3></summary>

```java
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

// распределение задач по кругу между исполнителями <T>
public class CircularList<T> {
  // ключ — количество обращений, значение — список исполнителей
  private final TreeMap<Integer, List<T>> elements = new TreeMap<>();

  // list — список исполнителей, обязательный параметр
  public CircularList(List<T> list) {
    if (list == null || list.size() == 0) return;
    this.elements.put(0, new ArrayList<>(list));
  }

  // возвращаем первый элемент с наименьшим количеством обращений
  public synchronized T getOne() {
    // вынимаем из карты первую запись с наименьшим количеством обращений
    Map.Entry<Integer, List<T>> entry = this.elements.pollFirstEntry();
    Integer key = entry.getKey();
    List<T> value = entry.getValue();
    // вынимаем из списка первый элемент
    T element = value.remove(0);
    // если в списке ещё что-то осталось — помещаем обратно в карту
    if (value.size() > 0) this.elements.put(key, value);
    // берём из карты следующий список с большим количеством обращений
    List<T> newValue = this.elements.get(key + 1);
    // если его нет — создаём новый список
    if (newValue == null) newValue = new ArrayList<>();
    // добавляем текущий элемент
    newValue.add(element);
    // помещаем обновлённый список в карту
    this.elements.put(key + 1, newValue);
    // если достигнут максимум — сбрасываем счётчики и обновляем карту
    if (Integer.MAX_VALUE - key < 10) this.reset();
    // возвращаем первый элемент с наименьшим количеством обращений
    return element;
  }

  // возвращаем первый элемент с наименьшим количеством
  // обращений, которого нет в списке отбора — filter
  public synchronized T getOne(List<T> filter) {
    // некорректно задан фильтр — отбор не применяется
    if (filter == null || filter.size() == 0) return getOne();
    Integer key = -1;
    List<T> value;
    T element = null;
    // обходим записи карты
    for (Map.Entry<Integer, List<T>> entry : this.elements.entrySet()) {
      key = entry.getKey();
      value = entry.getValue();
      // обходим элементы списка
      for (T el : value) {
        // если элемента нет в фильтре
        if (!filter.contains(el)) {
          // элемент найден
          element = el;
          // удаляем элемент из списка
          value.remove(el);
          // если в списке ничего не осталось — удаляем запись карты
          if (value.size() == 0) this.elements.remove(key);
          // выходим из цикла
          break;
        }
      }
      // если элемент найден — выходим из цикла
      if (element != null) break;
    }
    // если элемент не найден — фильтр не применяется
    if (element == null) return getOne();
    // берём из карты следующий список с большим количеством обращений
    List<T> newValue = this.elements.get(key + 1);
    // если его нет — создаём новый список
    if (newValue == null) newValue = new ArrayList<>();
    // добавляем текущий элемент
    newValue.add(element);
    // помещаем обновлённый список в карту
    this.elements.put(key + 1, newValue);
    // если достигнут максимум — сбрасываем счётчики и обновляем карту
    if (Integer.MAX_VALUE - key < 10) this.reset();
    // возвращаем первый элемент с наименьшим количеством обращений
    return element;
  }

  // возвращаем указанный элемент независимо от количества обращений
  public synchronized T getOne(T filterIn) {
    // некорректно задан фильтр — отбор не применяется
    if (filterIn == null) return getOne();
    // обходим записи карты
    for (Map.Entry<Integer, List<T>> entry : this.elements.entrySet()) {
      Integer key = entry.getKey();
      List<T> value = entry.getValue();
      // обходим элементы списка
      for (T element : value) {
        // если элемент найден
        if (filterIn.equals(element)) {
          // удаляем этот элемент из списка
          value.remove(element);
          // если в списке ничего не осталось — удаляем запись карты
          if (value.size() == 0) this.elements.remove(key);
          // берём из карты следующий список с большим количеством обращений
          List<T> newValue = this.elements.get(key + 1);
          // если его нет — создаём новый список
          if (newValue == null) newValue = new ArrayList<>();
          // добавляем текущий элемент
          newValue.add(element);
          // помещаем обновлённый список в карту
          this.elements.put(key + 1, newValue);
          // если достигнут максимум — сбрасываем счётчики и обновляем карту
          if (Integer.MAX_VALUE - key < 10) this.reset();
          // возвращаем отфильтрованный элемент
          return element;
        }
      }
    }
    // если элемент не найден — фильтр не применяется
    return getOne();
  }

  // возвращаем текущее состояние карты
  public synchronized String status() {
    return elements.toString();
  }

  @Override
  public synchronized String toString() {
    return elements.toString();
  }

  // сбрасываем счётчики и обновляем карту
  private synchronized void reset() {
    List<T> newList = new ArrayList<>();
    while (this.elements.size() > 0)
      newList.addAll(this.elements.pollFirstEntry().getValue());
    this.elements.put(0, newList);
  }
}
```

</details>

---

<details>
<summary><h3 id="Test.java">Test.java</h3></summary>

```java
import java.util.Arrays;
import java.util.List;

// быстрое тестирование — запускаем методы в одном потоке
class Test {
  public static void main(String[] args) {
    List<String> executors = Arrays.asList("A", "B", "C", "D");
    CircularList<String> list = new CircularList<>(executors);
    System.out.println(list);
    // {0=[A, B, C, D]}
    for (int i = 0; i < 10; i++)
      System.out.print(list.getOne(Arrays.asList("A")) + " ");
    // B C D B C D B C D B 
    System.out.println();
    System.out.println(list.status());
    // {0=[A], 3=[C, D], 4=[B]}
    for (int i = 0; i < 3; i++)
      System.out.print(list.getOne("D") + " ");
    // D D D 
    System.out.println();
    System.out.println(list.status());
    // {0=[A], 3=[C], 4=[B], 6=[D]}
    for (int i = 0; i < 14; i++)
      System.out.print(list.getOne() + " ");
    // A A A C A B C A B C A D B C 
    System.out.println();
    System.out.println(list.status());
    // {6=[A], 7=[D, B, C]}
  }
}
```

</details>

---

<details>
<summary><h3 id="Test2.java">Test2.java</h3></summary>

```java
import java.util.Arrays;
import java.util.List;

// долгое тестирование — запускаем методы в многопоточном режиме
class Test2 {
  public static void main(String[] args) {
    final List<String> executors = Arrays.asList("A", "B", "C", "D");
    final CircularList<String> list = new CircularList<>(executors);
    Runnable r1 = new Runnable() {
      @Override
      public void run() {
        for (int i = 0; i < 1000; i++) {
          String test = list.getOne(Arrays.asList("A"));
          if (!executors.contains(test))
            System.out.println("Error!");
        }
      }
    };
    Runnable r2 = new Runnable() {
      @Override
      public void run() {
        for (int i = 0; i < 300; i++) {
          String test = list.getOne("D");
          if (!executors.contains(test))
            System.out.println("Error!");
        }
      }
    };
    Runnable r3 = new Runnable() {
      @Override
      public void run() {
        for (int i = 0; i < 1400; i++) {
          String test = list.getOne();
          if (!executors.contains(test))
            System.out.println("Error!");
        }
      }
    };
    long time = System.currentTimeMillis();
    for (int i = 0; i < 4000000; i++) {
      new Thread(r1).start();
      new Thread(r2).start();
      new Thread(r3).start();
      if (i % 1000000 == 0) {
        System.out.print(list.status() + " :: ");
        System.out.println(System.currentTimeMillis() - time);
      }
    }
    System.out.print(list.status() + " == ");
    System.out.println(System.currentTimeMillis() - time);
    // {0=[D], 1=[B, C, A]} :: 3
    // {674162345=[A], 674162346=[B, C], 674163331=[D]} :: 953920
    // {1348883478=[A], 1348883589=[C], 1348883590=[B], 1348884772=[D]} :: 1912645
    // {2024396005=[A], 2024396024=[B, C], 2024396481=[D]} :: 2878158
    // {551625032=[A], 551625033=[B, C], 551625061=[D]} == 3847930
  }
}
```

</details>

---

© Головин Г.Г., Код с комментариями, 2023
